package cuiyt.datastructure.heap;

import cuiyt.datastructure.searchtree.printer.BinaryTreeInfo;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author cyt
 * @describe 二叉堆
 * @create 2021-01-10 12:37
 */
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;


    public BinaryHeap(E[] data, Comparator<E> comparator) {
        super(comparator);
        if (data == null || data.length == 0) {
            elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = data.length;
            int cap = Math.max(data.length, DEFAULT_CAPACITY);
            elements = (E[]) new Object[cap];
            for (int i = 0; i < data.length; i++) {
                elements[i] = data[i];
            }
            heapify();
        }

    }

    /**
     * 批量建堆
     */
    private void heapify() {
/*        for (int i = 0; i < size; i++) {
            siftUp(i);
        }*/

        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }


    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public BinaryHeap() {
        this(null, null);
    }

    private void checkHeapEmpty() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    private void checkElementNotNull(E element) {
        if (element == null) {
            throw new IllegalArgumentException("heap element is not null");
        }
    }

    @Override
    public void clear() {
        size = 0;
        Arrays.fill(elements, null);
    }

    @Override
    public void add(E element) {
        checkElementNotNull(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        siftUp2(size - 1);
    }

    private void siftUp(int index) {
        // 当前位置的元素， 此后需要用它来与它的父节点比较
        E element = elements[index];
        while (index > 0) {
            int pindex = (index - 1) / 2;
            int res = compare(element, elements[pindex]);
            if (res < 0) {
                return;
            }
            // 开始交换
            E temp = element;
            elements[index] = elements[pindex];
            elements[pindex] = temp;
            index = pindex;
        }
    }

    /**
     * 改变原有每次都交换元素的方法 为 找到最终的位置之后 一次赋值
     *
     * @param index
     */
    private void siftUp2(int index) {
        // 当前位置的元素， 此后需要用它来与它的父节点比较
        E element = elements[index];
        while (index > 0) {
            int pindex = (index - 1) / 2;
            int res = compare(element, elements[pindex]);
            if (res < 0) {
                break;
            }
            elements[index] = elements[pindex];
            index = pindex;
        }
        elements[index] = element;
    }

    @Override
    public E get() {
        checkHeapEmpty();
        return elements[0];
    }

    @Override
    public E remove() {
        checkHeapEmpty();
        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;

        siftDown(0);
        return root;
    }

    /**
     * 让index位置的元素下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子节点的索引 == 非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证index位置是非叶子节点
        while (index < half) {
            // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点
            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }
            if (compare(element, child) >= 0) {
                break;
            }
            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

    @Override
    public E replace(E element) {
        checkElementNotNull(element);

        E root = null;
        if (size == 0) {
            elements[size++] = element;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity + " =  > > " + newCapacity);
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index = (int) node;
        index = (index << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index = (int) node;
        index = (index << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        return elements[(int) node];
    }
}
